//1.哈希表
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head==nullptr || head->next == nullptr) 
            return nullptr;
        unordered_set<ListNode *> hashmap;
        
        ListNode * slow =head;
        
        while(slow) {
            if(hashmap.count(slow))
                return slow;
           
            hashmap.insert(slow);
            slow = slow->next;
        }
        return nullptr;
    }
};
//2.空间复杂度：O(1)---快慢指针（看题解）
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast != nullptr) {
            slow = slow->next;
            if (fast->next == nullptr) {
                return nullptr;
            }
            fast = fast->next->next;
            if (fast == slow) {
                ListNode *ptr = head;
                while (ptr != slow) {
                    ptr = ptr->next;
                    slow = slow->next;
                }
                return ptr;
            }
        }
        return nullptr;
    }
};



